공급망 혼란 📉
선박들이 뒤죽박죽된 순서로 도착하고 있습니다. 우리는 혼란도 지표 (역전쌍의 수)를 계산하여 인공지능 교통 관제 시스템을 최적화해야 합니다.
역전쌍이란 무엇인가요?
인덱스 쌍 $(i, j)$가 다음 조건을 만족하면 역전쌍입니다:
- $i < j$ (선박 $i$가 $j$보다 먼저 도착함)
- $A[i] > A[j]$ (선박 $i$의 우선순위 ID가 더 큼)
분석 🔍
예시 순서: [2, 4, 1, 3, 5]
- ❌ (2, 1): 2가 1보다 먼저 오지만, 2 > 1
- ❌ (4, 1): 4가 1보다 먼저 오지만, 4 > 1
- ❌ (4, 3): 4가 3보다 먼저 오지만, 4 > 3
- 총 혼란도: 3개의 역전쌍
과제
단순 반복 구조는 $O(N^2)$.
for i in range(n):
for j in range(i+1, n): ...
for j in range(i+1, n): ...
$N=100,000$일 경우 약 100억 번의 연산이 필요합니다. 결과: 시간 초과 발생.